// 赫夫曼树-静态链表表示法（考试用）
#ifndef HUFFMAN_STATIC_H
#define HUFFMAN_STATIC_H

/// @brief 赫夫曼树节点
typedef struct
{
	char data;				 // 节点值
	int weight;				 // 节点权值
	int parent, left, right; // 双亲节点与左右孩子的下标，若双亲/孩子节点为空则为-1
} HTNode;

/// @brief 霍夫曼树结构体，用节点数组来表示整棵树
typedef struct
{
	HTNode *nodes; // 霍夫曼树的所有节点构成的数组（前面leafCount个节点是叶子节点，后面leafCount - 1个节点是度为2的节点，根据霍夫曼树性质：叶子节点总是比度为2的节点多一个）
	int leafCount; // 叶子节点数
	int root;	   // 根节点索引
} HuffmanTree;

/// @brief 霍夫曼编码结果，Code表示单个编码结果，CodeMap是全部编码结果的集合
typedef struct
{
	char data;	// 字符
	char *code; // 对应编码字符串
} Code;

typedef struct
{
	Code *codeResults; // Code编码结果数组
	int count;		   // 编码个数
} CodeMap;

/// @brief 从霍夫曼树节点中选择出两个最小的节点
/// @param nodes 由全部叶子节点组成的节点数组，先开始每个节点视为只有根节点的树，容量为2n - 1（霍夫曼树性质：度为0的节点总是比度为2的节点多一个，因此数组前面n个是存放的是初始全部的叶子节点指针，后面留出的n - 1的空间用于存放每次比较合并后的子树的节点）
/// @param count nodes数组中有效节点个数
/// @param n1 传入一个整型指针以获取第一个被选择的节点的下标
/// @param n2 传入一个整型指针以获取第二个被选择的节点的下标
void selectMin(HTNode *, int, int *, int *);

/// @brief 构造一个霍夫曼树
/// @param nodes 传入用于构造树的元素集合
/// @param weight 权值集合
/// @param count 叶子节点数
/// @return 霍夫曼树对象指针
HuffmanTree *createHuffmanTree(char[], int[], int);

/// @brief 计算霍夫曼树的带权路径长度
/// @param tree 霍夫曼树对象指针
/// @return 带权路径长度
int getWPL(HuffmanTree *);

/// @brief 霍夫曼编码
/// @param tree 霍夫曼树对象指针
/// @return 编码结果
CodeMap *huffmanCoding(HuffmanTree *);

/// @brief 先序遍历打印霍夫曼树
/// @param tree 霍夫曼树对象指针
/// @param nodeIndex 开始遍历的霍夫曼树节点下标
void preorderTraverse(HuffmanTree *, int);

/// @brief 中序遍历打印霍夫曼树
/// @param tree 霍夫曼树对象指针
/// @param nodeIndex 开始遍历的霍夫曼树节点下标
void inorderTraverse(HuffmanTree *, int);

/// @brief 后序遍历打印霍夫曼树
/// @param tree 霍夫曼树对象指针
/// @param nodeIndex 开始遍历的霍夫曼树节点下标
void postorderTraverse(HuffmanTree *, int);

#include "./huffman-tree-static.c"

#endif